# coding: utf-8
# 选择排序实现

# 用[low,high)模拟切片，节省内存
# 切片arr[start:end]是重新生成一个列表，与原列表独立，会增加空间复杂度
def smallest(lst,low,high):
    # len=high-low
    lstLen=high-low
    if lstLen<=0:
        return None
    if lstLen<=1:
        return lst[low]
    pos=low
    val=lst[pos]
    for i in range(low,high):
        if lst[i]<val:
            pos=i
            val=lst[i]
    return {"pos":pos, "val": val}

def selectionSort(lst):
    lstLen=len(lst)
    if lstLen<=1:
        return
    # [0,len-2] python的range和exchange太方便了
    for i in range(0,lstLen-1):
        info=smallest(lst,i,lstLen)
        if info!=None:
            pos=info['pos']
            lst[i],lst[pos]=lst[pos],lst[i]

lst = [1,11,2,22,3,33,-1,2,3]
print("smallest:",smallest(lst,0,6))
selectionSort(lst)
print(lst)
